home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 12 / Cream of the Crop 12 (Part II) / Cream of the Crop 12 (Part II).iso / OS2 / DIKUMUD.ZIP / HASH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-30  |  4.2 KB  |  216 lines
  1. /*
  2.   SillyMUD Distribution V1.1b             (c) 1993 SillyMUD Developement
  3.  
  4.   See license.doc for distribution terms.   SillyMUD is based on DIKUMUD
  5. */
  6.  
  7. #include <stdio.h>
  8.  
  9. #include "protos.h"
  10.  
  11. #define    HASH_KEY(ht,key)    ( (((unsigned int)(key)) * 17) % (ht)->table_size )
  12.  
  13. void init_hash_table(struct hash_header    *ht, int rec_size, int table_size)
  14. {
  15.   ht->rec_size = rec_size;
  16.   ht->table_size = table_size;
  17.   ht->buckets = (void*)calloc(sizeof(struct hash_link**), table_size);
  18.   ht->keylist = (void*)malloc(sizeof(ht->keylist)*(ht->klistsize=128));
  19.   ht->klistlen = 0;
  20. }
  21.  
  22. void init_world(struct room_data *room_db[])
  23. {
  24.  
  25.    bzero(room_db, sizeof(struct room_data *) * WORLD_SIZE);  /* zero out the world */
  26.  
  27. }
  28.  
  29.  
  30. void destroy_hash_table(struct hash_header *ht, void (*gman)())
  31. {
  32.   int    i;
  33.   struct hash_link *scan, *temp;
  34.  
  35.   for (i=0; i<ht->table_size; i++)
  36.     for (scan = ht->buckets[i]; scan; ) {
  37.       temp = scan->next;
  38.       (*gman)(scan->data);
  39.       free(scan);
  40.       scan = temp;
  41.     }
  42.   free(ht->buckets);
  43.   free(ht->keylist);
  44. }
  45.  
  46.  
  47. void _hash_enter(struct hash_header *ht, int key, void *data)
  48.  
  49. { /* precondition: there is no entry for <key> yet */
  50.   struct hash_link *temp;
  51.   int    i;
  52.  
  53.   temp = (struct hash_link *)malloc(sizeof(struct hash_link));
  54.   temp->key = key;
  55.   temp->next = ht->buckets[HASH_KEY(ht,key)];
  56.   temp->data = data;
  57.   ht->buckets[HASH_KEY(ht,key)] = temp;
  58.   if (ht->klistlen >= ht->klistsize) {
  59.     ht->keylist = (void*)realloc(ht->keylist,sizeof(*ht->keylist)*
  60.                  (ht->klistsize*=2));
  61.   }
  62.   for (i=ht->klistlen; i>=0; i--) {
  63.     if (ht->keylist[i-1]<key) {
  64.       ht->keylist[i] = key;
  65.       break;
  66.     }
  67.     ht->keylist[i] = ht->keylist[i-1];
  68.   }
  69.   ht->klistlen++;
  70. }
  71.  
  72. struct room_data *room_find( struct room_data *room_db[], int key)
  73. {
  74.    return((key<WORLD_SIZE&&key>-1)?room_db[key]:0);
  75. }
  76.  
  77. void *hash_find(struct hash_header *ht, int key)
  78. {
  79.   struct hash_link    *scan;
  80.  
  81.   scan = ht->buckets[HASH_KEY(ht,key)];
  82.  
  83.   while (scan && scan->key != key)
  84.     scan = scan->next;
  85.  
  86.   return scan ? scan->data : NULL;
  87. }
  88.  
  89. int room_enter(struct room_data *rb[], int key, struct room_data *rm)
  90. {
  91.    struct room_data *temp;
  92.    
  93.    temp = room_find(rb, key);
  94.    if (temp) return(0);
  95.  
  96.    rb[key] = rm;
  97.    return(1);
  98.  
  99. }
  100.  
  101. int hash_enter(struct hash_header *ht, int key, void *data)
  102. {
  103.   void    *temp;
  104.   temp = hash_find(ht, key);
  105.   if (temp)
  106.     return 0;
  107.  
  108.   _hash_enter(ht, key, data);
  109.   return 1;
  110. }
  111.  
  112. struct room_data *room_find_or_create(struct room_data *rb[], int key)
  113. {
  114.   struct room_data *rv;
  115.  
  116.   rv = room_find(rb, key);
  117.   if (rv)
  118.     return rv;
  119.  
  120.   rv = (struct room_data *)malloc(sizeof(struct room_data));
  121.  
  122.   rb[key] = rv;
  123.     
  124.   return rv;
  125. }
  126.  
  127. void *hash_find_or_create(struct hash_header *ht, int key)
  128. {
  129.   void    *rval;
  130.  
  131.   rval = hash_find(ht, key);
  132.   if (rval)
  133.     return rval;
  134.  
  135.   rval = (void*)malloc(ht->rec_size);
  136.   _hash_enter(ht,key,rval);
  137.   return rval;
  138. }
  139.  
  140. int room_remove(struct room_data *rb[], int key)
  141. {
  142.  
  143.    struct room_data *tmp;
  144.  
  145.    tmp = room_find(rb, key);
  146.  
  147.    if (tmp) {
  148.      rb[key] = 0;
  149.      free(tmp);
  150.    } 
  151.    return(0);
  152. }
  153.  
  154. void *hash_remove(struct hash_header *ht, int key)
  155. {
  156.   struct hash_link    **scan;
  157.  
  158.   scan = ht->buckets +HASH_KEY(ht,key);
  159.  
  160.   while (*scan && (*scan)->key != key)
  161.     scan = &(*scan)->next;
  162.  
  163.   if (*scan) {
  164.     int    i;
  165.  
  166.     struct hash_link *temp, *aux;
  167.     temp = (*scan)->data;
  168.     aux = *scan;
  169.     *scan = aux->next;
  170.     free(aux);
  171.  
  172.     for (i=0; i<ht->klistlen; i++)
  173.       if (ht->keylist[i]==key)
  174.     break;
  175.  
  176.     if (i<ht->klistlen) {
  177.       bcopy(ht->keylist+i+1, ht->keylist+i, 
  178.         (ht->klistlen-i)*sizeof(*ht->keylist));
  179.       ht->klistlen--;
  180.     }
  181.  
  182.     return temp;
  183.   }
  184.  
  185.   return NULL;
  186. }
  187.  
  188. void room_iterate(struct room_data *rb[], void (*func)(), void *cdata)
  189. {
  190.   register int    i;
  191.   for (i=0; i<WORLD_SIZE; i++) {
  192.     struct room_data  *temp;
  193.   
  194.     temp = room_find(rb, i);
  195.     if (temp) {
  196.        (*func)(i, temp, cdata);
  197.     }
  198.   }
  199. }
  200.  
  201.  
  202. void hash_iterate(struct hash_header *ht, void (*func)(), void *cdata)
  203. {
  204.   int    i;
  205.   for (i=0; i<ht->klistlen; i++) {
  206.     void    *temp;
  207.     register int key;
  208.  
  209.     key = ht->keylist[i];
  210.     temp = hash_find(ht, key);
  211.     (*func)(key, temp, cdata);
  212.     if (ht->keylist[i]!=key) /* They must have deleted this room */
  213.       i--;    /* Hit this slot again. */
  214.   }
  215. }
  216.